#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include<unordered_map>
#include<iostream>

using namespace std;

//vector<int> findSubstring(string s, vector<string>& words)
//{
//    unordered_map<string, int> m2;
//    int left = 0, right = 0;
//    int len = words[0].size();
//    int ct = 0;
//    vector<int> ret;
//
//    for (auto& e : words)
//    {
//        m2[e]++;
//    }
//
//    int slen = s.size();
//    for (int i = 0; i < len; i++)
//    {
//        unordered_map<string, int> m1;
//        ct = 0;
//        if (i == 0)
//            slen += len;
//        else
//            slen = s.size();
//        for (left = i, right = left; right + len < slen; )
//        {
//            string w(s.begin() + right, s.begin() + right + len);
//            m1[w]++;
//            right += len;
//
//            if (m1[w] <= m2[w])
//            {
//                ct++;
//            }
//
//            if (right/len - left/len + 1 > words.size())
//            {
//                if (ct == words.size())
//                {
//                    ret.push_back(left);
//                }
//                if (m1[{s.begin() + left, s.begin() + left + len}]
//                    <= m2[{s.begin() + left, s.begin() + left + len}])
//                {
//                    ct--;
//                }
//                m1[{s.begin() + left, s.begin() + left + len}]--;
//                left += len;
//            }
//
//        }
//    }
//    return ret;
//}


vector<int> findSubstring(string s, vector<string>& words) {
    unordered_map<string, int> m2;
    int left = 0, right = 0;
    int len = words[0].size();
    int ct = 0;
    vector<int> ret;

    for (auto& e : words) {
        m2[e]++;
    }

    int slen = s.size();
    for (int i = 0; i < len; i++) {
        unordered_map<string, int> m1;
        ct = 0;

        for (left = i, right = left; right + len <= s.size();) {
            string w(s.begin() + right, s.begin() + right + len);
            m1[w]++;
            right += len;

            if (m1[w] <= m2[w]) {
                ct++;
            }

            if ((right - left) / len >= words.size()) {
                if (ct == words.size()) {
                    ret.push_back(left);
                }
                if (m1[{s.begin() + left, s.begin() + left + len}] <=
                    m2[{s.begin() + left, s.begin() + left + len}]) {
                    ct--;
                }
                m1[{s.begin() + left, s.begin() + left + len}]--;
                left += len;
            }
        }
    }
    return ret;
}
int main()
{
    /*string s = "barfoothefoobarman";
    vector<string> words = { "foo", "bar" };*/

   /* string s = "wordgoodgoodgoodbestword";
    vector<string> words = { "word","good","best","good" };*/
    
    /*string s = "barfoofoobarthefoobarman";
    vector<string> words = { "bar", "foo", "the" };*/

    string s = "aaaaaaaaaaaaaa";
    vector<string> words = { "aa", "aa" };

    vector<int> ret = findSubstring(s, words);
    for (auto e : ret)
    {
        cout << e << " ";
    }
    cout << endl;
	return 0;
}